﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Task06_BalansedTreeGen
{
	class Tree
	{
		private Tree leftChild;
		private Tree rightChild;

		public int ChildrenCount { get; private set; }

		public int? Value { get; set; }

		public Tree LeftChild
		{
			get
			{
				if (leftChild == null)
				{
					leftChild = new Tree();
					ChildrenCount++;
				}
				return leftChild;
			}
		}

		public Tree RightChild
		{
			get
			{
				if (rightChild == null)
				{
					rightChild = new Tree();
					ChildrenCount++;
				}
				return rightChild;
			}
		}

		public Tree()
		{
			this.Value = null;
		}

		public Tree GetChild(int number)
		{
			if (number == 0)
			{
				return LeftChild;
			}
			else
			{
				return RightChild;
			}
		}

		public void AddNewValue(int value)
		{
			if (this.Value == null)
			{
				this.Value = value;
				return;
			}

			if (value > this.Value)
			{
				this.RightChild.AddNewValue(value);
				return;
			}

			if (value < this.Value)
			{
				this.LeftChild.AddNewValue(value);
				return;
			}
		}
	}
	class Program
	{
		static void Main(string[] args)
		{
			Tree tree = new Tree();

			int startValue = -300;
			//balansed tree has 2^n - 1 nodes
			int numbersCount = 262143;
			List<int> values = new List<int>();

			for (int i = 0; i < numbersCount; i++)
			{
				values.Add(startValue + i);
			}

			GenerateBalansedTree(0, numbersCount - 1, values, tree);

			StringBuilder result = new StringBuilder();
			PrintTree(tree, result);
			Console.WriteLine(result);
		}

		private static void GenerateBalansedTree(int startIndex, int endIndex, List<int> values, Tree tree)
		{
			if (startIndex >= endIndex)
			{
				tree.AddNewValue(values[startIndex]);
				return;
			}
			else
			{
				int middle = startIndex + (endIndex - startIndex) / 2;
				tree.AddNewValue(values[middle]);
				GenerateBalansedTree(startIndex, middle - 1, values, tree);
				GenerateBalansedTree(middle + 1, endIndex, values, tree);
			}
		}

		private static bool PrintTree(Tree root, StringBuilder sb)
		{
			if (root.ChildrenCount > 0)
			{
				sb.Append('(');
				sb.Append(root.Value);
				sb.Append("->");
				for (int i = 0; i < root.ChildrenCount; i++)
				{
					PrintTree(root.GetChild(i), sb);
					if (i < root.ChildrenCount - 1)
					{
						sb.Append(',');
					}
				}
				sb.Append(')');
			}
			else
			{
				if (root.Value == null)
				{
					sb.Append('x');
				}
				else
				{
					sb.Append(root.Value);
				}
			}

			return true;
		}
	}
}
